#ifndef _DFA_OPER_IMPL
#define _DFA_OPER_IMPL

#include <iostream>

#include "Share.h"
#include "Dfa_base_str.h"
using namespace dfa_base_str;

/* implement dfa operation
		Pos_set first_val;
		Pos_set last_val;
		Lex_oper &reg;
		bool calculated;			// to label calculated
*/
Kleen &Kleen::cal() {				// kleen
	first_val = reg.first();		//calculate first value
	last_val = reg.last();
	calculated = true;
	return *this;
}
One_more &One_more::cal() {					// One_more
	first_val = reg.first();
	last_val = reg.last();
	One_more::nullabel = reg.nul();
	calculated = true;
	return *this;
}
Zero_one &Zero_one::cal() {					// zero_one
	first_val = reg.first();		//calculate first value
	last_val = reg.last();
	calculated = true;
	return *this;
}
Concate &Concate::cal() {				// concatenation
	bool l_eplilon=false, r_eplilon=false;
	dfa_base_str::Eplilon *eplilon;
	if( dfa_base_str::Start_line *start_line = dynamic_cast<Start_line *> (&left) ) {
		last_val = right.last();								// first value is empty
		nullabel = right.nul();
		return *this;
	} else if( eplilon = dynamic_cast<Eplilon *> (&left) )
		l_eplilon = true;
	if( eplilon = dynamic_cast<Eplilon *> (&right) )
		r_eplilon = true;
	if( l_eplilon & r_eplilon ) {
		nullabel = true;							// first_val = last_val = empty
		return *this;
	} else if( l_eplilon ) {
		first_val = right.first();
		last_val = right.last();
		nullabel = right.nul();
		return *this;
	} else if( r_eplilon ) {
		first_val = left.first();
		last_val = left.last();
		nullabel = left.nul();
		return  *this;
	}
	bool l_nul = left.nul(), r_nul = right.nul();			// normal case
	if( l_nul ) {
		first_val += left.first();
		first_val += right.first();
	} else {
		first_val += left.first();
	}
	if( r_nul ) {
		last_val += left.last();
		last_val += right.last();
	} else
		last_val += right.last();
	if( l_nul && r_nul )
		nullabel = true;
	else
		nullabel = false;
	calculated = true;
	return *this;
}
Union &Union::cal() {					// union
	first_val += left.first();
	first_val += right.first();
	last_val += left.last();
	last_val += right.last();
	nullabel = left.nul() | right.nul();
	calculated = true;
	return *this;
}
Suffix &Suffix::cal() {					// suffix
	bool l_eplilon=false, r_eplilon=false;
	dfa_base_str::Eplilon *eplilon;
	if( eplilon = dynamic_cast<Eplilon *> (&left) )
		l_eplilon = true;
	if( eplilon = dynamic_cast<Eplilon *> (&right) )
		r_eplilon = true;
	if( l_eplilon & r_eplilon ) {
		nullabel = true;							// first_val = last_val = empty
		return *this;
	} else if( l_eplilon ) {
		first_val = right.first();
		last_val = right.last();
		nullabel = right.nul();
		return *this;
	} else if( r_eplilon ) {
		first_val = left.first();
		last_val = left.last();
		nullabel = left.nul();
		return  *this;
	}
	bool l_nul = left.nul(), r_nul = right.nul();
	if( l_nul ) {
		first_val += left.first();
		first_val += right.first();
	} else {
		first_val += left.first();
	}
	if( r_nul ) {
		last_val += left.last();
		last_val += right.last();
	} else
		last_val += right.last();
	if( l_nul && r_nul )
		nullabel = true;
	else
		nullabel = false;
	calculated = true;
	return *this;
}

bool dfa_base_str::print_reg_tree(std::ostream &cout, Lex_oper &tree) {
	using namespace std;
	void print_pos_set(ostream &out,const Pos_set &s);
	Lex_oper *reg_tree = &tree;
	if( Reg_base *base = dynamic_cast<Reg_base *> (reg_tree) ) {
		const int pos = *((base->first()).begin());
		cout << "Reg_base" << pos << ": ";		// Reg_base: element
		const mylib::Set<char> &elets = base->element();
		for(mylib::Set<char>::const_iterator C=elets.begin(); C!=elets.end(); C++ )
			cout << *C;
		cout << std::endl;
	} else if( dfa_base_str::End_mark *end = dynamic_cast<End_mark *> (reg_tree) ) {
		;
	} else if( Start *start = dynamic_cast<Start *> (reg_tree) ) {	// <pattern>
		cout << "Start<>: " << endl;
		print_reg_tree(cout, start->child());
	} else if( Start_line *start_line= dynamic_cast<Start_line *> (reg_tree) )		// ^
		cout << "Start of one line\n";
	else if( Kleen *kleen = dynamic_cast<Kleen *>(reg_tree) ) {
		cout << "Kleen: " << "first <";
		cout << kleen->first();
		cout << '>' << "\tlast<";
		cout << kleen->last();
		cout << ">\n";
		print_reg_tree(cout, kleen->child());
	} else if( One_more *one_more = dynamic_cast<One_more *>(reg_tree) ) {
		cout << "One_more: " << "first <";
		cout << one_more->first();
		cout << '>' << "\tlast<";
		cout << one_more->last();
		cout << ">\n";
		print_reg_tree(cout, one_more->child());
	} else if( Zero_one *zero_one = dynamic_cast<Zero_one *>(reg_tree)) {
		cout << "zero_one: " << "first <";
		cout << zero_one->first();
		cout << '>' << "\tlast<";
		cout << zero_one->last();
		cout << ">\n";
		print_reg_tree(cout, zero_one->child());
	} else if( Concate *concate = dynamic_cast<Concate *>(reg_tree)) {
		cout << "Concate: " << "first <";
		cout << concate->first();
		cout << '>' << "\tlast <";
		cout << concate->last();
		cout << '>' << endl;
		print_reg_tree(cout, concate->l_child());
		print_reg_tree(cout, concate->r_child());
	} else if( Union *un = dynamic_cast<Union *>(reg_tree)) {
		cout << "Union: " << "first <";
		cout << un->first();
		cout << '>' << "\tlast <";
		cout << un->last();
		cout << '>' << endl;
		print_reg_tree(cout, un->l_child());
		print_reg_tree(cout, un->r_child());
	} else if( Suffix *suffix = dynamic_cast<Suffix *>(reg_tree)) {
		cout << "Suffix: " << "first <";
		cout << suffix->first();
		cout << '>' << "\tlast <";
		cout << suffix->last();
		cout << '>' << endl;
		print_reg_tree(cout, suffix->l_child());
		print_reg_tree(cout, suffix->r_child());
	} else if ( Eplilon *eplilon = dynamic_cast<Eplilon *>(reg_tree))
		cout << "Eplilon" << endl;
	else {
		cout << "Undefine regular operation\n";
		dfa_base_str::Lex_oper::Invalid_input();
	}
	return 0;			// Ok
}
bool dfa_base_str::del_reg_tree(Lex_oper &tree) {
	Lex_oper *reg_tree = &tree;
	if( Reg_base *base = dynamic_cast<Reg_base *>(reg_tree) ) {
		delete base;
	} else if( dfa_base_str::End_mark *end = dynamic_cast<End_mark *> (reg_tree) ) {
		delete end;
	} else if( Start *start = dynamic_cast<Start *> (reg_tree) ) {
		delete start;
	} else if( Start_line *start_line= dynamic_cast<Start_line *> (reg_tree) )
		delete start_line;
	else if( Kleen *kleen = dynamic_cast<Kleen *>(reg_tree) ) {
		del_reg_tree(kleen->child());
		delete kleen;
	} else if( One_more *one_more = dynamic_cast<One_more *>(reg_tree) ) {
		del_reg_tree(one_more->child());
		delete one_more;
	} else if( Zero_one *zero_one = dynamic_cast<Zero_one *>(reg_tree)) {
		del_reg_tree(zero_one->child());
		delete zero_one;
	} else if( Concate *concate = dynamic_cast<Concate *>(reg_tree)) {
		del_reg_tree(concate->l_child());
		del_reg_tree(concate->r_child());
		delete concate;
	} else if( Union *un = dynamic_cast<Union *>(reg_tree)) {
		del_reg_tree(un->l_child());
		del_reg_tree(un->r_child());
		delete un;
	} else if( Suffix *suffix = dynamic_cast<Suffix *>(reg_tree)) {
		del_reg_tree(suffix->l_child());
		del_reg_tree(suffix->r_child());
		delete suffix;
	} else if ( Eplilon *eplilon = dynamic_cast<Eplilon *>(reg_tree))
		delete eplilon;
	else {
		dfa_base_str::Lex_oper::Invalid_input();
	}
	return 0;
}
#include <stack>
namespace copyn_reg_tree_loc {
	const bool LEFT = false;
	const bool RIGHT = true;
	std::stack<dfa_base_str::Lex_oper *> &copyn_tree(dfa_base_str::Lex_oper &tree, size_t n, bool pos);//copy n tree
}
#include <stack>		// use for subtree
dfa_base_str::Lex_oper *dfa_base_str::copyn_reg_tree(const dfa_base_str::Lex_oper &tree, size_t n) {
	using namespace std;
	using namespace copyn_reg_tree_loc;
	if( n <= 0 )
		return 0;
	stack<dfa_base_str::Lex_oper *> &trees = copyn_tree(*const_cast<dfa_base_str::Lex_oper *>(&tree), n,LEFT );// copy n times
	dfa_base_str::Lex_oper *reg=0;
	try {
		while( -- n > 0 ) {		// concate n-1 times
			reg = trees.top();
			trees.pop();
			dfa_base_str::Concate *concate = new dfa_base_str::Concate(*reg, *trees.top());
			trees.pop();
			trees.push(concate);
		}
	} catch(...) {
		if( reg )
			dfa_base_str::del_reg_tree(*reg);
		while( !trees.empty() ) {
			dfa_base_str::del_reg_tree(*trees.top());
			trees.pop();
		}
		throw dfa_base_str::Out_of_mem();
	}
	reg = trees.top();
	trees.pop();					// clear the tree
	return reg;
}
//copy n tree
std::stack<dfa_base_str::Lex_oper *> &copyn_reg_tree_loc::copyn_tree(dfa_base_str::Lex_oper &tree, size_t n, bool pos) {
	using namespace dfa_base_str;
	static std::stack<Lex_oper *> l_tree, r_tree;		// left subtree and right subtree
	Lex_oper *new_node;
	Lex_oper *reg_tree = &tree;
	std::stack<Lex_oper *> temp_tree, &des_tree = (pos==LEFT) ? l_tree : r_tree;
	try {
		if( Reg_base *base = dynamic_cast<Reg_base *>(reg_tree) ) {
			while( n-- > 0 ) {
				new_node = new Reg_base(base->element());
				des_tree.push(new_node);
			}
		} else if( dynamic_cast<End_mark *> (reg_tree) ) {
			while( n-- > 0 ) {
				new_node = new End_mark();
				des_tree.push(new_node);
			}
		} else if(Start *start = dynamic_cast<Start *> (reg_tree) ) {
			copyn_tree(start->child(), n, LEFT);
			size_t t = n;
			while( n-- > 0 ) {
				new_node = new Start(*l_tree.top());
				l_tree.pop();
				temp_tree.push(new_node);
			}
			while( t-- > 0 ) {
				des_tree.push(temp_tree.top());
				temp_tree.pop();
			}
		} else if( dynamic_cast<Start_line *> (reg_tree) ) {
			while( n-- > 0 ) {
				new_node = new Start_line();
				des_tree.push(new_node);
			}
		} else if( Kleen *kleen = dynamic_cast<Kleen *>(reg_tree) ) {
			copyn_tree(kleen->child(), n, LEFT);		// first copy children
			size_t t = n;
			while( n-- > 0 ) {
				new_node = new Kleen(*l_tree.top());
				l_tree.pop();
				temp_tree.push(new_node);
			}
			while( t-- > 0 ) {
				des_tree.push(temp_tree.top());
				temp_tree.pop();
			}
		} else if( One_more *one_more = dynamic_cast<One_more *>(reg_tree) ) {
			copyn_tree(one_more->child(), n, LEFT);
			size_t t = n;
			while( n-- > 0 ) {
				new_node = new One_more(*l_tree.top());
				l_tree.pop();
				temp_tree.push(new_node);
			}
			while( t-- > 0 ) {
				des_tree.push(temp_tree.top());
				temp_tree.pop();
			}
		} else if( Zero_one *zero_one = dynamic_cast<Zero_one *>(reg_tree)) {
			copyn_tree(zero_one->child(), n, LEFT);
			size_t t = n;
			while( n-- > 0 ) {
				new_node = new Zero_one(*l_tree.top());
				l_tree.pop();
				temp_tree.push(new_node);
			}
			while( t-- > 0 ) {
				des_tree.push(temp_tree.top());
				temp_tree.pop();
			}
		} else if(Concate *concate = dynamic_cast<Concate *>(reg_tree)) {
			copyn_tree(concate->l_child(), n, LEFT);
			copyn_tree(concate->r_child(), n, RIGHT);
			size_t t = n;
			while( n-- > 0 ) {
				Lex_oper *right=r_tree.top();
				r_tree.pop();
				Lex_oper *left=l_tree.top();
				l_tree.pop();
				new_node = new Concate(*left, *right);
				temp_tree.push(new_node);
			}
			while( t-- > 0 ) {
				des_tree.push(temp_tree.top());
				temp_tree.pop();
			}
		} else if(Union *un = dynamic_cast<Union *>(reg_tree)) {
			copyn_tree(un->l_child(), n, LEFT);
			copyn_tree(un->r_child(), n, RIGHT);
			size_t t = n;
			while( n-- > 0 ) {
				Lex_oper *right=r_tree.top();
				r_tree.pop();
				Lex_oper *left=l_tree.top();
				l_tree.pop();
				new_node = new Union(*left, *right);
				temp_tree.push(new_node);
			}
			while( t-- > 0 ) {
				des_tree.push(temp_tree.top());
				temp_tree.pop();
			}
		} else if( Suffix *suffix = dynamic_cast<Suffix *>(reg_tree)) {
			copyn_tree(suffix->l_child(), n, LEFT);
			copyn_tree(suffix->r_child(), n, RIGHT);
			size_t t = n;
			while( n-- > 0 ) {
				Lex_oper *right=r_tree.top();
				r_tree.pop();
				Lex_oper *left=l_tree.top();
				l_tree.pop();
				new_node = new Suffix(*left, *right);
				temp_tree.push(new_node);
			}
			while( t-- > 0 ) {
				des_tree.push(temp_tree.top());
				temp_tree.pop();
			}
		} else if (Eplilon *eplilon = dynamic_cast<Eplilon *>(reg_tree))
			while( n-- > 0 ) {
				new_node = new Eplilon();
				des_tree.push(new_node);
			}
		else {
			dfa_base_str::Lex_oper::Invalid_input();
		}
		return l_tree;
	} catch(...) {
		while( !temp_tree.empty() ) {
			dfa_base_str::del_reg_tree(*temp_tree.top());
			temp_tree.pop();
		}
		while( !r_tree.empty() ) {
			dfa_base_str::del_reg_tree(*r_tree.top());
			r_tree.pop();
		}
		while( !l_tree.empty() ) {
			dfa_base_str::del_reg_tree(*l_tree.top());
			l_tree.pop();
		}
		throw dfa_base_str::Out_of_mem();
	}
}
#endif
